In a database management system, a graph has one or more nodes (or vertices) that are connected by one or more edges (or links). Each node may have a type or class and at least one value associated with it. A graph database refers to a collection of data that is stored in a graph data structure implemented in a database management system.
Analysts often have the need to look for patterns in data that can be represented as subgraphs. Using a pattern as a query mechanism is called subgraph isomorphism, graph pattern matching, or pattern query.
To reduce the search time needed for a particular pattern query, it may be desirable to produce an optimal deconstruction of the pattern query. Currently, such deconstruction is accomplished through a combination of visual inspection, experience, experimentation, or other techniques. However, such ad hoc approaches are not practical for complex pattern query searches. For example, although visual cues may be evident from the visual depiction of the pattern, in practice many pattern queries are prepared in pattern query language (PQL) and the PQL representation of the pattern query does not provide such visual cues. Also, it is not desirable to require an analyst to have expertise in query plan optimization.